package com.sheng.leetcode.year2023.swordfingerofferspecial.day02;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * @author liusheng
 * @date 2023/03/02
 * <p>
 * 剑指 Offer II 005. 单词长度的最大乘积<p>
 * <p>
 * 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。<p>
 * 假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。<p>
 * <p>
 * 示例 1:<p>
 * 输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]<p>
 * 输出: 16<p>
 * 解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。<p>
 * <p>
 * 示例 2:<p>
 * 输入: words = ["a","ab","abc","d","cd","bcd","abcd"]<p>
 * 输出: 4<p>
 * 解释: 这两个单词为 "ab", "cd"。<p>
 * <p>
 * 示例 3:<p>
 * 输入: words = ["a","aa","aaa","aaaa"]<p>
 * 输出: 0<p>
 * 解释: 不存在这样的两个单词。<p>
 * <p>
 * 提示：<p>
 * 2 <= words.length <= 1000<p>
 * 1 <= words[i].length <= 1000<p>
 * words[i] 仅包含小写字母<p>
 * <p>
 * 注意：本题与主站 318 题相同：<a href="https://leetcode-cn.com/problems/maximum-product-of-word-lengths/">主站 318</a><p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/aseY1I">剑指 Offer II 005. 单词长度的最大乘积</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword005 {

    @Test
    public void test01() {
//        String[] words = {"abcw", "baz", "foo", "bar", "fxyz", "abcdef"};
//        String[] words = {"a", "ab", "abc", "d", "cd", "bcd", "abcd"};
        String[] words = {"a", "aa", "aaa", "aaaa"};
        System.out.println(new Solution005().maxProduct(words));
    }
}

class Solution005 {
    public int maxProduct(String[] words) {
        int max = 0;
        for (int i = 0; i < words.length; i++) {
            Set<String> set = new HashSet<>();
            for (int i1 = 0; i1 < words[i].length(); i1++) {
                set.add(words[i].charAt(i1) + "");
            }
            for (int j = 0; j < words.length; j++) {
                if (i != j) {
                    boolean flag = true;
                    for (String str : set) {
                        if (words[j].contains(str)) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        max = Math.max(max, words[i].length() * words[j].length());
                    }
                }
            }
        }
        return max;
    }
}
